package com.leetcodehot.problems;

public class problems1458 {
    /**
     * f[i][j]=max(f[i−1][j−1]+xij,xij,f[i−1][j],f[i][j−1],f[i−1][j−1])
     * 注意到状态转移方程中有一个可以优化的地方，这是因为 f[i−1][j] 以及 f[i][j−1] 对应的状态转移方程中已经包含了 f[i−1][j−1]
     * f[i][j]=max(f[i−1][j−1]+xij,xij,f[i−1][j],f[i][j−1])
     * 动态规划的边界条件也非常容易处理。在对 f[i][j] 进行转移时，我们只要处理那些没有超出边界的项就行了。最后的答案即为 f[m−1][n−1]
     */
    public int maxDotProduct(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[][] f = new int[m][n];

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int xij = nums1[i] * nums2[j];
                f[i][j] = xij;
                if (i > 0) {
                    f[i][j] = Math.max(f[i][j], f[i - 1][j]);
                }
                if (j > 0) {
                    f[i][j] = Math.max(f[i][j], f[i][j - 1]);
                }
                if (i > 0 && j > 0) {
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + xij);
                }
            }
        }

        return f[m - 1][n - 1];
    }
}
